public class T {
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {

    TreeNode node=null;

    private boolean dfs(TreeNode root,TreeNode p, TreeNode q){

        if(root==null){
            return false;
        }

        boolean lson=dfs(root.left,p,q);
        boolean rson=dfs(root.right,p,q);

        if((lson&&rson)||((p.val==root.val||q.val==root.val)&&(rson||lson))){
            node=root;
        }


        return lson||rson||(p.val==root.val)||(q.val==root.val);



    }





    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {


        dfs(root,p,q);


        return node;






    }
}